package 题目集.动态规划.状压dp;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;

/**
 * todo：1.如果这是双向图，如何应对。2.这题允许重复走，如何解决 某乡有n个村庄(1<=n<=20)，有一个售货员，他要到各个村庄去售货
 * 各村庄之间的路程s(1<=s<=1000)是已知的 且A村到B村的路程，与B到A的路大多不同(有向带权图)
 * 为了提高效率，他从商店出发到每个村庄一次，然后返回商店所在的村， 假设商店所在的村庄为1 他不知道选择什么样的路线才能使所走的路程最短
 * 请你帮他选择一条最短的路 测试链接 : https://www.luogu.com.cn/problem/P1171 注：题目给出的表示图的方式是邻接矩阵
 * 思路： 没啥思路，全排列吧，枚举以1为起点的所有合法方案+终点到起点的屈居，对其求个min
 */
public class ch03_TSP问题 {
	static int n;
	static int maxN = 21;
	static int[][] maze = new int[maxN][maxN];
	static boolean[] vis = new boolean[maxN];

	public static void main(String[] args) {
		Reader2 sc = new Reader2(System.in);
		n = sc.nextInt();
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				maze[i][j] = sc.nextInt();
			}
		}
		vis[1] = true;
//		int res=dfs(1,1,0);
		finalPath = (1 << n) - 1;
		int res = dpDfs(1, 1);
		System.out.println(res);
	}

	/**
	 * 朴素dfs
	 *
	 * @param cur
	 * @param cnt
	 * @return
	 */
	public static int dfs(int cur, int cnt) {
		if (cnt == n) {
			return maze[cur][1];
		}
		int ans = Integer.MAX_VALUE;
		for (int to = 1; to <= n; to++) {
			if (!vis[to]) {
				vis[to] = true;
				ans = Math.min(ans, dfs(to, cnt + 1)+maze[cur][to]);
				vis[to] = false;
			}
		}
		return ans;
	}

	static int[][] dp = new int[maxN][1 << 20];
	static int finalPath;

	public static int dpDfs(int cur, int path) {
		if (dp[cur][path] != 0) {
			return dp[cur][path];
		}
		if (path == finalPath) {
			dp[cur][path] = maze[cur][1];
		} else {
			dp[cur][path] = Integer.MAX_VALUE;
			for (int i = 1; i <= n; i++) {
				int to = 1 << (i - 1);
				if ((path & to) == 0) {
					dp[cur][path] = Math.min(dp[cur][path], dpDfs(i, path | to) + maze[cur][i]);
				}
			}
		}
		return dp[cur][path];
	}

	static class Reader2 {
		static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

		public Reader2(Object... o) {
		}

		public int nextInt() {
			try {
				in.nextToken();
			} catch (Exception ignored) {
			}
			return (int) in.nval;
		}
	}
}
